package graph;

import java.util.ArrayList;

public class GraphByNode {
    static class Node {
        public int src;//起点
        public int dest;//终点
        public int weight;//权重
        public Node next;

        public Node(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public char[] arrayV;
    public ArrayList<Node> edgList;//存储边
    public boolean isDirect;

    public GraphByNode(boolean isDirect, int size) {
        this.arrayV = new char[size];
        edgList = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            edgList.add(null);
        }
        this.isDirect = isDirect;
    }

    public void initArrayV(char[] array) {
        for (int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
        }
    }

    public void addEdge(char srcV, char destV, int weight) {
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);
        addEdgeChild(srcIndex, destIndex, weight);
        if (!isDirect) {
            addEdgeChild(destIndex, srcIndex, weight);
        }
    }

    private void addEdgeChild(int srcIndex, int destIndex, int weight) {
        Node cur = edgList.get(srcIndex);
        while (cur != null) {
            //是否存在该值
            if (cur.dest == destIndex) {
                return;
            }
            cur = cur.next;
        }
        //不存在,创建
        Node newNode = new Node(srcIndex, destIndex, weight);
        newNode.next = edgList.get(srcIndex);
        edgList.set(srcIndex, newNode);
    }

    private int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if (arrayV[i] == v) {
                return i;
            }
        }
        return -1;
    }

    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i]);
            Node cur = edgList.get(i);
            while (cur != null) {
                System.out.print("->" + arrayV[cur.dest]);
                cur = cur.next;
            }
            System.out.println();
        }
    }

    public int getDevOfV(char v) {
        int srcIndex = getIndexOfV(v);
        int count = 0;
        Node cur = edgList.get(srcIndex);
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        //有向图额外考虑入度
        if (isDirect) {
            for (int i = 0; i < arrayV.length; i++) {
                //入度不需要考虑从本身出发的点
                if (i == srcIndex) {
                    continue;
                } else {
                    cur = edgList.get(i);
                    while (cur != null) {
                        if (cur.dest == srcIndex) {
                            count++;
                        }
                        cur = cur.next;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {

        GraphByNode graph = new GraphByNode(false, 4);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.initArrayV(array);

        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);

        System.out.println("getDevOfV:: "+graph.getDevOfV('A'));
        graph.printGraph();
    }
}
